Jeg skriver i øjeblikket en grundlæggende parser for en XML-smag. Som en øvelse implementerer jeg en LL-tabeldrevet parser. Dette er mit eksempel på BNF-grammatik: % token navn datastreng %% / * LL (1) * / doc: elem elem: "<" open_tag open_tag: navn attr close_tag close_tag: ">" elem_or_data "" | "/>" ; elem_or_data: "<" open_tag elem_or_data | data elem_or_data | / * epsilon * / ; attr: navn ":" streng attr | / * epsilon * / ; Er denne grammatik korrekt? Hver terminal bogstavelig er mellem anførselstegn. De abstrakte terminaler er angivet med% token. Jeg koder en håndskrevet lexer for at konvertere mit input til en tokensliste. Hvordan ville jeg tokenisere de abstrakte terminaler?
2021-03-03 08:10:37
Den klassiske tilgang ville være at skrive et regulært udtryk (eller en anden genkender) for hver mulig terminal.
Hvad du kalder "abstrakte" terminaler, som er helt konkrete, er faktisk terminaler, hvis tilknyttede mønstre genkender mere end en mulig inputstreng. Den streng, der faktisk er genkendt (eller en eller anden beregnet funktion af den streng), skal sendes til parseren som symbolets semantiske værdi.
Nominelt kører tokeniseren på hvert punkt i inputstrengen alle genkendere og vælger den der har den længste match. (Dette er den såkaldte "maksimale munch" -regel.) Dette kan normalt optimeres, især hvis alle mønstre er regulære udtryk. (F) lex vil f.eks. Gøre den optimering for dig.
En komplikation i din sag er, at tokenisering af dit sprog er kontekstafhængig. Især når målet er elem_or_data, er de eneste mulige tokens <,